The use of remote computing services, such as remote program execution services and remote data storage services has greatly increased in recent years. Customers may purchase these services from a computing resource service provider, and customer applications may be distributed over multiple virtual machine instances running on one or more computing systems. In some cases, these virtual machine instances run under a virtualization layer that exposes a logical volume stored on partitions distributed between data storage servers. However, determining how volume partitions should be distributed to achieve optimal performance, durability, and availability can be challenging, particularly when conditions, constraints, and partition locations can change over time.